package practice;

import java.util.*;

public class Day37 {
    //最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[n][m];
    }
    //柱状图最大矩形
    public int largestRectangleArea(int[] heights) {
        //首尾各加一个0，为了让第一个和最后一个元素进行计算的时候更加方便
        int[] newHeights = new int[heights.length+2];
        for(int i = 1; i < heights.length+1; i++) {
            newHeights[i] = heights[i-1];
        }
        //存储的是下标
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for(int i = 0; i < newHeights.length; i++) {
            while(!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]) {
                int cur = stack.pop();
                //这里前一个元素一定是比当前元素小的
                res = Math.max(res,newHeights[cur] * (i-stack.peek()-1));
            }
            stack.push(i);
        }
        return res;
    }

    //LRU缓存(map+双向链表实现)
    class LRUCache {

        class Node {
            int key;
            int value;
            Node prev;
            Node next;
            public Node(){}
            public Node(int k,int v) {
                key = k;
                value = v;
            }
        }
        //维护一个双向链表，现在创建一个头部伪节点和一个尾部伪节点
        Node head;
        Node tail;
        int size;
        Map<Integer,Node> map;
        int n;
        public LRUCache(int capacity) {
            head = new Node();
            tail = new Node();
            map = new HashMap<>();
            n = capacity;
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            Node v = map.getOrDefault(key,null);
            if(v == null) {
                return -1;
            }else {
                //维护当前值，将当前值放到链表的头部
                moveToHead(v);
                return v.value;
            }
        }

        public void put(int key, int value) {
            Node v = map.getOrDefault(key,null);
            if(v == null) {
                //将其放入到map中，然后维护双向链表
                Node newNode = new Node(key,value);
                map.put(key,newNode);
                addToHead(newNode);
                size++;
                if(size > n) {
                    //如果超出容量，删除链表末尾元素
                    Node ta = moveTail();
                    map.remove(ta.key);
                    size--;
                }
            }else {
                //先进行map中元素的修改，然后维护双向链表，将元素放到头部
                v.value = value;
                moveToHead(v);
            }
        }
        private void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        private void addToHead(Node node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }
        private void moveToHead(Node node) {
            removeNode(node);
            addToHead(node);
        }
        private Node moveTail() {
            Node ret = tail.prev;
            removeNode(ret);
            return ret;
        }
    }

    //验证二叉搜索树
    public boolean isValidBST(TreeNode root) {
        return isValidBSTChild(root,Long.MAX_VALUE,Long.MIN_VALUE);
    }
    public boolean isValidBSTChild(TreeNode node,long up,long down) {
        if(node == null) {
            return true;
        }
        if(node.val <= down || node.val >= up) {
            return false;
        }
        return isValidBSTChild(node.left,node.val,down) && isValidBSTChild(node.right,up,node.val);

    }
    //三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int k = 2;
        while (k < n) {
            int target = -nums[k];
            //在k之前找到和为target的值
            int i = 0;
            int j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > target) {
                    j--;
                } else if (nums[i] + nums[j] < target) {
                    i++;
                } else {
                    //添加之前应该去重
                    while (i < j && nums[i] == nums[i + 1]) {
                        i++;
                    }
                    while (j > i && nums[j] == nums[j - 1]) {
                        j--;
                    }
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ret.add(list);
                    i++;
                    j--;
                }
            }
            while (k + 1 < n && nums[k] == nums[k + 1]) {
                k++;
            }
            k++;
        }
        return ret;
    }
    //完全平方数
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j*j <= i; j++) {
                dp[i] = Math.min(dp[i],1 + dp[i-j*j]);
            }
        }
        return dp[n];
    }

    //
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for(int i = 1; i <= m; i++) {
            dp[0][i] = i;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        word1 = " " + word1;
        word2 = " " + word2;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(word1.charAt(i) != word2.charAt(j)) {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
                }else {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[n][m];
    }
    //零钱兑换
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for(int i = 1; i <= amount; i++) {
            dp[i] = 0x3f3f3f3f;
        }
        int n = coins.length;
        for(int i = 1; i <= amount; i++) {
            for(int j = 0; j < n; j++) {
                if(i - coins[j] >= 0) {
                    dp[i] = Math.min(dp[i-coins[j]] + 1,dp[i]);
                }
            }
        }
        return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount];
    }
    int[] preorder;
    int[] inorder;
    public TreeNode buildTree(int[] pre, int[] in) {
        preorder = pre;
        inorder = in;
        return buildTreeChild(0,in.length-1);
    }
    int k = 0;
    private TreeNode buildTreeChild(int inS,int inE) {
        if(inS > inE) {
            return null;
        }
        int i = 0;
        for(i = inS; i <= inE; i++) {
            //在inorder中找到preorder[i]
            if(preorder[k] == inorder[i]) {
                k++;
                break;
            }
        }
        TreeNode root = new TreeNode(inorder[i]);
        root.left = buildTreeChild(inS,i-1);
        root.right = buildTreeChild(i+1,inE);
        return root;
    }
    //寻找旋转数组中的最小值
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}
